1. Field of the Invention
The present invention relates to random number generators (RNG) and more particularly to a method and means that uses an analog-to-digital (A/D) conversion process on random noise to produce an output from an analog-to-digital converter and then applies a reductive mapping process to the A/D converter output to transform it into a uniformly distributed random variable.
2. Description of the Prior Art
With the proliferation of digital computers, and the increasing rates at which they operate, an unprecedented demand for random numbers has arisen and accordingly RNGs. The myriad applications which benefit from RNGs are as diverse and ubiquitous as national security and home entertainment, e.g., cryptography and computer games. Earlier, random numbers were needed in order to solve problems by experimental probability procedures run on the first digital computers. The early experimental procedures have since been developed into the sophisticated probabilistic algorithms that are now run on contemporary computing platforms resulting in a corresponding increase in demand. Over the same history, the scope of digital computer applications has expanded manifold, and the advantages provided to these applications by methods which require random numbers continue to be recognized. Of greatest importance in such applications are random sequences which have the uniform probability distribution, the ideal output of computer languages"" xe2x80x9crandom number functions.xe2x80x9d Accordingly, a measure of RNG quality in this regard is that it have a small bias, i.e., a small difference between the distribution of the RNG output and the uniform distribution. The random physical phenomena employed in implementing RNGs pose unique problems in terms of harnessing the phenomena to provide, as digital signals, the needed uniformly distributed random numbers.
It is, of course, desirable that the numbers provided to a random number application be generated by means which produce actual randomness, since any correlation among them is detrimental. However, the physical phenomena useful for providing rapid, automatic random means present a problem in that they do not exhibit the uniform distribution required of the RNG output. One widely practiced solution is to circumvent this problem by substituting uniformly distributed non-random sequences in lieu of random sequences, whenever practicable. Such pseudo-random sequences are generated by deterministic algorithmic processes, e.g., modular multiplication, which, by careful selection of parameters, yield sequences that are devoid of obvious patterns. Because no random phenomenon is involved, all elements of pseudo-random sequences are, necessarily, causally related and the sequences may be accurately predicted and replicated. This replication property is fundamental for pseudo-random applications, e.g., the RSA cryptosystem (see U.S. Pat. No. 4,405,829), in which the sender uses a modular exponentiation to obscure meaning in transit and the recipient uses an inverse modular exponentiation to regenerate the sender""s plaintext. However, for random number applications, this replication property is a liability, since, e.g., in order to maximize security, RSA keys (i.e., exponents and modulus) are generated exclusively by random means.
Several other prior art solutions to the problem generate random time periods as means to randomly select numbers produced by deterministic means. Examples include the so-called xe2x80x9celectronic roulette wheelxe2x80x9d used to produce Rand""s well-known table (see Rand Corporation. (1966) A Million Random Digits with 100,000 Normal Deviates, The Free Press. Glencoe Ill.), and the method involving radiology by which, xe2x80x9cRandom-numbers modulo-M are produced by stopping the rapidly advancing [modulo-M] counter at the random time, determined by an electron arrival of the G-M [Geiger-Mueller] tube [from a sample of 90Sr]xe2x80x9d (see SCHMIDT, H. (1970) xe2x80x9cQuantum-mechanical random-number generatorxe2x80x9d, Journal of Applied Physics, 41, 462-468). Another recent method in this regard employs user actions, e.g., keystrokes, as means to randomly select numbers from software counters in order to generate cryptographic keys for secure interchange via the Internet. The generation rates provided by the second method are obviously much higher than those provided by the latter method, but the rates are limited to 80,000 bit/sec by an estimated G-M tube limit of 10,000 counts per second. Although random frequency pulses may be produced at high rates by entirely electronic means, to significantly exceed a rate of 80,000 bit/sec would require digital counters that may be clocked at SHF or EHF frequencies, or a cumbersome plurality of slower apparatus.
Further prior art solutions use deterministic means to distort random electronic noise, which is normally distributed, in order to provide a 1-bit random variable. One example subjects the noise to successive stages of clipping, amplifying, and sampling, whereby the normal distribution is thus directly divided in two, with the probability of each fraction mapped to one of the two possible digits (see NELSON, R. D., BRADISH, G. J., and DOBYNS, Y. H. (1989) xe2x80x9cRandom event generator qualification, calibration and analysis.xe2x80x9d Princeton University School of Engineering/Applied Sciences; and U.S. Pat. No. 5,830,064). Another example uses a comparator to severely amplify the difference between the instantaneous output of two sources. In practice, maintaining the approximate coincidence of division and median in the former example, and of the two medians in the latter example, within a tolerance that provides a bias as small as the quantum-mechanical RNG, e.g.,  less than 3xc3x9710xe2x88x926, necessitates extreme precision and periodic calibration.
It is believed that the limitations of the prior art methods and means have resulted in speed and cost constraints on execution of random number applications which cannot tolerate non-random characteristics. These random number applications include, e.g., cryptographic key generation. The limitations have also resulted in the use of pseudo-random numbers in other applications for which high speed is essential and non-random characteristics may be tolerated, for instance, computer simulations for which unwanted correlation is not catastrophic. Still other applications for which no compromise is feasible have had to be abandoned. Lastly, in the case of probabilistic, xe2x80x9cMonte Carloxe2x80x9d methods that may be practiced with pseudo-random numbers, computer resources consumed by pseudo-random generator algorithms represent a reduction of resources to the application itself
Consequently, there is a need in the art for a method and means that provide uniformly distributed random number sequences.
Objects:
It is accordingly an object of the present invention to provide an improved method and means of generating random number sequences having uniform distribution.
It is another object of the invention to provide an improved random number generator for use in any situation which benefits from random number sequences.
It is a further object of the invention to provide a high-speed RNG of particularly small bias.
It is a still further object of the invention to provide an electronic RNG which has no periodic calibration requirements.
It is an additional object of the invention to provide an improved RNG for use in applications benefiting from random number sequences, particularly applications wherein it is most preferred that an RNG be fabricated as an integrated circuit (RNG-IC).
It is also an object of the present invention to provide an improved method and means of generating random number sequences that is automatic and free of radiological considerations.
The present invention is directed to providing an improved method and means for generating random number sequences and particularly as embodied in a random number generator (RNG). The RNG embodiment provides uniformly distributed random number sequences that are usable in a considerable number of applications in the art. The RNG of the invention is of the type known as a xe2x80x9cnondeterministic random number generator,xe2x80x9d i.e., the present invention uses phenomena which are believed to be truly random and there is no known method for predicting or replicating the number sequences it provides. The invention utilizes combinations of four main elements: a noise source, a compressor, an A/D converter, and a xe2x80x9creduction functionxe2x80x9d, i.e., a circuit which performs a reductive mapping process. The preferred embodiment includes all four elements, but other embodiments comprising combinations of a lesser number have demonstrated utility. In accordance with the invention an A/D converter (ADC) is used to produce sequences of voltage (or current) measurements of the output of a source of random noise. Inasmuch as the digital output of the A/D converter is a random variable, this output does provide random sequences of numbers, but the mere combination of the noise source and ADC alone does not constitute a xe2x80x9crandom number generatorxe2x80x9d, since the term implies a uniform distribution. Preferably, the random noise measured by the A/D converter is produced by applying a reverse-bias to a P-N junction, i.e., a semiconductor noise source, and the A/D converter is a linear converter, which thus outputs random sequences with a normal probability distribution. Alternatively, using a logarithmic, A-law, or other appropriate, A/D converter will provide other distributions, as will non-linear amplification of the noise, or an alternative noise source. The fact that the invention thus provides a method and means for generating normally distributed random sequences, or various alternatives, renders it adaptable for use with special random number applications.
Greater utility is achieved in accordance with the invention by applying a reductive mapping process to the A/D converter output sequences in order to produce random sequences with the uniform distribution and thus provide an RNG. Preferably, this mapping process is a reduction modulo-M, where M less than  less than 2n for an n-bit A/D converter, so that random numbers 0, 1, . . . (Mxe2x88x921) are generated at the A/D converter sampling frequency. Thus the RNG may generate uniformly distributed random number sequences at the high-speeds of available A/D converters. Also, greater efficiency is achieved by using a compressor to amplify random noise. The compressor automatically increases gain for low level (i.e., standard deviation of the voltage or current) input and reduces gain for high level input. By using a compressor to stabilize the standard deviation, the reduction function may use a greater modulus, M, for any given maximum RNG bias, and RNG output rate=(log2 M)(sampling frequency) bit/sec. Thus, in the preferred embodiment, the random noise from the noise source is amplified by the compressor, the amplified noise is provided to the A/D converter for measurement, and the digital measurements are reduced by the reduction function to produce uniformly distributed random sequences, which constitute the output of the RNG. The RNG generates uniformly distributed random sequences of the numbers 0, 1, . . . (Mxe2x88x921) at the A/D converter sampling frequency.
Particular features provided by the invention include the novel use of an analog-to-digital (A/D) conversion process to produce voltage or current measurements of random noise in automatically generating random numbers, obviating any need of radioactive material, so that the RNG may be fabricated either from commercially available parts or as a single integrated circuit (RNG-IC). Also, the novel applying of a reductive mapping (i.e., an R to 1 mapping, R greater than 1) process to digital measurements of voltage or current enables the production of a low cost, high-speed, electronic RNG of particularly small bias. Further, the small bias of such an electronic RNG may be made free from periodic calibration requirements by newly using a signal compressor to amplify the random noise. By using synchronous digital processes, the RNG may be operated synchronously, so that it can be easily iterated into arrays coordinated by interleaving and paralleling methods well-known in the art. A particular embodiment of the invention in a personal computer may comprise a semiconductor noise source, radio-frequency compressor, 16-bit 100,000 sample/sec A/D converter, and computer-bus interface logic that reduces data modulo-256, that form an RNG which is automatic, uses no radioactive material, requires no periodic calibration, and generates random numbers synchronously at a constant rate of 800,000 bit/sec with a bias of less than 3xc3x9710xe2x88x9212, i.e., three parts per trillion. xe2x80x9cFurther, the small bias of such an electronic RNG may be made free from periodic calibration requirements by newly using a signal compressor to amplify the random noise. By using synchronous digital processes, the RNG may be operated synchronously, so that it can be easily iterated into arrays coordinated by interleaving and paralleling methods well-known in the art.xe2x80x9d